class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        dp = [[0 for _ in range(n2)] for _ in range(n1)]
        def get(i, j):
            if i < 0:
                return j + 1
            elif j < 0:
                return i + 1
            return dp[i][j]
        for i in range(n1):
            for j in range(n2):
                replace = get(i-1, j-1) + (0 if word1[i] == word2[j] else 1)
                delete = get(i-1, j) + 1
                insert = get(i, j-1) + 1
                dp[i][j] = min([replace, delete, insert])
        return get(n1-1, n2-1)



print(Solution().minDistance('horse', 'ros'))


